CF167E Wizards and Bets

首先，我们将所有源点与汇点筛出来，然后从每一个源点dfs求出它到各汇点的路径数，题目中保证源点与汇点数量相同，我们记为$cnt$。
那么，我们可以得到一个$cnt * cnt$的矩阵。

先考虑路径不相交的情况（似乎大家思路都是这样），题目求的是一个排列的逆序对数，记为$\tau(\sigma)$。那么，题目等价于求：

$\sum(-1)^{\tau(\sigma)}*\prod{f_{~i~\sigma_i}}$

其中，$f_{i~\sigma_i}$表示i号源点走到$\sigma_i$号汇点的路径数。

结合上文，不难很难想到行列式。然后，你会发现，矩阵的行列式就是答案。

然后，我们考虑路径相交的情况，发现答案不变。

显然，$(1 \to 4),(2 \to 5)$路径相交了

我们考虑交换$4,5$位置

还是相交的。

这虽然不能解决我们的问题，但我们发现，经过交换后，汇点序列的逆序对数奇偶性变了，也就是矩阵行列式的其中一项变号。同时，路径数却没有变。所以，两种情况相互抵消了！！！

所以，路径相交并不会影响答案，直接算行列式即可。

本代码由@Krain大佬修改，可能神似请见谅。

同时，求矩阵行列式时消元必须在整数范围内运算，需要用到辗转相除的高斯消元，此处不再赘述。

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 600;
int n , m , x , y , p , cnt;
int Ind[ MAXN + 5 ] , Outd[ MAXN + 5 ];
int s[ MAXN + 5 ][ MAXN + 5 ];
int tmp[ MAXN + 5 ] , f[ MAXN + 5 ][ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
vector< int > S , T;

int Mo( long long x ) {
	return ( x % p + p ) % p;
}
int Gauss( ) {
	int Sign = 1;
    for( int i = 1 ; i <= cnt ; i ++ ) {
    	for( int j = i + 1 ; j <= cnt ; j ++ ) {
    		int A = f[ i ][ i ] , B = f[ j ][ i ];
    		while( B ) {
    			int t = A / B; A %= B; swap( A , B );
    			for( int k = i ; k <= n ; k ++ )
    				f[ i ][ k ] = Mo( 1ll * f[ i ][ k ] - 1ll * t * f[ j ][ k ] );
    			
    			swap( f[ i ] , f[ j ] );
    			Sign *= -1;
			}
		}
    	if( !f[ i ][ i ] ) return 0;
    }
    int Ans = 1;
    for( int i = 1 ; i <= cnt ; i ++ )
        Ans = ( 1ll * Ans * f[ i ][ i ] ) % p;
    return Mo( 1ll * Ans * Sign );
}

bool vis[ MAXN + 5 ];
void dfs( int u ) {
	vis[ u ] = 1;
    if( !Outd[ u ] ) s[ u ][ u ] = 1;
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( !vis[ v ] ) dfs( v );
        for( int j = 0 ; j < T.size() ; j ++ )
        	s[ u ][ T[ j ] ] = Mo( 1ll * s[ u ][ T[ j ] ] + s[ v ][ T[ j ] ] );
    } 
}
int main( ) {
    scanf("%d %d %d",&n,&m,&p);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d",&x,&y);
        Graph[ x ].push_back( y );
        Outd[ x ] ++ , Ind[ y ] ++;
    }
    for( int i = 1 ; i <= n ; i ++ ) {
    	if( !Ind[ i ] )
    		S.push_back( i );
    	if( !Outd[ i ] )
    		T.push_back( i );
	}
    for( int i = 1 ; i <= n ; i ++ )
        if( !Ind[ i ] ) dfs( i );
    
    for( int i = 0 ; i < S.size() ; i ++ )
    	for( int j = 0 ; j < T.size() ; j ++ )
    		f[ i + 1 ][ j + 1 ] = s[ S[ i ] ][ T[ j ] ];
    cnt = S.size();
    printf("%d",Gauss( ));
    return 0;
}